package ljl.codetop;

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class _32_longest_valid_pars {

    /**
     * 暴力法吧，想不出来牛逼法
     * todo 超时了
     */
    static class tryout {
        byte[] buf;
        public int longestValidParentheses(String s) {
            buf = s.getBytes();
            int max = 0;
            for (int i = 0, l = s.length(); i < l; i++) {
                for (int j = i + 1; j < l; j++) {
                    if (valid(i, j)) {
                        if (j - i + 1 > max)
                            max = j - i + 1;
                    }
                }
            }
            return max;
        }
        boolean valid(int from, int to) {
            LinkedList<Character> q = new LinkedList<>();
            for (int i = from; i <= to; i++) {
                if (buf[i] == '(')
                    q.push('(');
                else if (q.isEmpty())
                    return false;
                else
                    q.pop();
            }
            return q.isEmpty();
        }
    }

    static class off1 {

        public int longestValidParentheses(String s) {
            int maxans = 0;
            // 每个位置表示当前位置结尾的括号对的最大长度
            int[] dp = new int[s.length()];
            for (int i = 1; i < s.length(); i++) {
                if (s.charAt(i) == ')') {
                    if (s.charAt(i - 1) == '(') {
                        dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                    }
                    else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                        dp[i] = dp[i - 1] + (i - dp[i - 1] >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                    }
                    maxans = Math.max(maxans, dp[i]);
                }
            }
            return maxans;
        }
    }

    static class copy_off1 {
        public int longestValidParentheses(String s) {
            int max = 0;
            int[] dp = new int[s.length()];
            for (int i = 1; i < s.length(); i++) {
                if (s.charAt(i) == ')') {
                    if (s.charAt(i - 1) == '(') {
                        dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                    } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                        dp[i] = dp[i - 1] + 2 + (i - dp[i - 1] >= 2 ? dp[i - dp[i - 1] - 2] : 0);
                    }
                    max = Math.max(max, dp[i]);
                }
            }
            return max;
        }
    }

    /**
     * todo 这个解法不知道哪来的奇技淫巧
     */
    static class off2 {
        public int longestValidParentheses(String s) {
            int max = 0;
            Deque<Integer> stack = new LinkedList<>();
            stack.push(-1);
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == '(') {
                    stack.push(i);
                } else {
                    stack.pop();
                    if (stack.isEmpty()) {
                        stack.push(i);
                    } else {
                        max = Math.max(max, i - stack.peek());
                    }
                }
            }
            return max;
        }
    }

    static class copy_off2 {
        public int longestValidParentheses(String s) {
            LinkedList<Integer> q = new LinkedList<>();
            q.push(-1);
            int max = 0;
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == '(')
                    q.push(i);
                else {
                    q.pop();
                    if (q.isEmpty())
                        q.push(i);
                    else
                        max = Math.max(max, i - q.peek());
                }
            }
            return max;
        }
    }

    static class off3 {
        public int longestValidParentheses(String s) {
            int left = 0, right = 0, maxlength = 0;
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == '(') {
                    left++;
                } else {
                    right++;
                }
                if (left == right) {
                    maxlength = Math.max(maxlength, 2 * right);
                } else if (right > left) {
                    left = right = 0;
                }
            }
            left = right = 0;
            for (int i = s.length() - 1; i >= 0; i--) {
                if (s.charAt(i) == '(') {
                    left++;
                } else {
                    right++;
                }
                if (left == right) {
                    maxlength = Math.max(maxlength, 2 * left);
                } else if (left > right) {
                    left = right = 0;
                }
            }
            return maxlength;
        }
    }

    /**
     * 想偷鸡，失败
     * 他说"处理不了 (() 的情况，因为 left 比 right 始终要大" 我想，我随时处理 right * 2 不就行了？
     * 其实还有一种情况没想到，就是 ()(()，此时算出来是四，实际上中间有不合法的括号
     */
    static class copy_off3_failed {
        public int longestValidParentheses(String s) {
            int left = 0;
            int right = 0;
            int max = 0;
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == '(')
                    left++;
                else {
                    right++;
                    if (left < right) {
                        left = right = 0;
                    } else {
                        max = Math.max(max, right * 2);
                    }
                }
            }
            return max;
        }
    }

    /**
     * 没什么特别好的办法，老老实实遍历两遍完事了，装啥逼呢？
     */
    static class copy_off3 {
        public int longestValidParentheses(String s) {
            int left = 0, right = 0, max = 0;
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == '(') left++;
                else right++;
                if (right > left) left = right = 0;
                else if (left == right) max = Math.max(left * 2, max);
            }
            left = right = 0;
            for (int i = s.length() - 1; i >= 0; i--) {
                if (s.charAt(i) == '(') left++;
                else right++;
                if (left > right) left = right = 0;
                else if (left == right) max = Math.max(left * 2, max);
            }
            return max;
        }
    }
}
